13. 程序运行效率 Efficiency

时间复杂度（Time Complexity） 大致描述了某个算法其运行时间随数据规模增大而增长的趋势。其取算法运行时间与数据规模之间的函数的阶，而忽略增长较小的部分。一些记号如下：

$\mathcal{O}$ 符号：渐进上界。
$\mathrm{\Omega }$ 符号：渐进下界。
$\mathrm{\Theta }$ 符号：渐进上下界相等。

例如：

• 遍历一个长度为 $n$ 的列表的时间复杂度为 $\mathrm{\Theta }(n)$。
• 归并排序一个长度为 $n$ 的列表的时间复杂度为 $\mathrm{\Theta }(n\log n)$。
• 朴素的递归计算斐波那契数列的第 $n$ 项的时间复杂度为 $\mathrm{\Theta }(n!)$。

与时间复杂度类似，算法占用的额外空间随数据规模增大而增长的趋势可以用 空间复杂度（Space Complexity） 描述。记号与时间复杂度相同。

Python 解释器存在内存管理机制，会自动将所有不处于 活跃环境 中的帧占用的内存回收。活跃环境指的是当前正在执行的函数所处的环境与该环境的所有父环境。

当程序执行递归计算会涉及到大量重复计算时，可以考虑使用记忆化，通过空间换时间的方式加速计算。一个典型的记忆化装饰器函数如下：

def memo(f):
	cache = dict()
	def memorized(arg):
		if arg not in cache:
			cache[arg] = f(arg)
		return cache[arg]
	return memorized